Modeling and analysis of the time behavior of dynamic systems is of wide interest in various fields of science and engineering. Because of the complexity of many current dynamic systems, “realistic models” of such dynamic systems often prohibit exact numerical or analytical evaluation of the system. For example, in an extremely wide variety of applications in military, civilian, and scientific computations such as for “war scenarios,” video games and queueing theory with applications to banking, cellular networks, wireless networks, manufacturing design, aircraft design and scientific computing, the dynamic systems running the applications are too complex to perform numerical or analytical evaluations on the systems. As a result, simulation of such systems generally remains the accepted tractable method by which to evaluate the systems. One type of simulation that has emerged is Discrete Event Simulation (DES), which discretizes the updates of the simulated system at event occurrence instances.
While the simulation of such complex systems generally remains the accepted tractable method by which to evaluate the systems, conducting simulations is often a time consuming experience. In this regard, once a simulation model has been specified for the system, the simulation run can require an unnecessarily long time to execute due to either the objective of the simulation or the nature of the simulation model. To reduce the time necessary to execute a simulation, importance sampling methods can be implemented in the model. As such, faster simulations can be obtained by using more computational resources, particularly, modem supercomputers that utilize multiple processing elements (PEs) operating in parallel.
To efficiently utilize modem supercomputers requires massively parallel implementations of dynamic algorithms for various physical, chemical, and biological processes. For many of these there are well-known and routinely used schemes, such as serial Monte Carlo (MC) schemes. Dynamic MC simulations are invaluable tools for investigating the evolution of complex systems. For a wide range of systems it is plausible to assume (and in rare cases it is possible to derive) that attempts to update the state of the system form a Poisson process. The basic notion is that time is continuous, and the discrete events (update attempts) occur instantaneously. The state of the system remains constant between events. It is worthwhile to note that the standard random-sequential update schemes (easily implementable on serial computers) produce this dynamic for “free”: the waiting-time distribution for the attempts to update each subsystem or component is geometrical and approaches the exponential distribution in the large-system limit. This uniquely characterizes the Poisson process.
The parallel implementation of such dynamic MC algorithms belongs to the class of parallel discrete event simulation (PDES), which is one of the most challenging areas in parallel computing and has numerous applications not only in the physical sciences, but also in computer science, queueing theory, and economics. For example, in lattice Ising models the discrete events are spin-flip attempts, while in queueing systems they are job arrivals. Typically, when a PDES is executed, the PDES repeatedly processes the occurrence of events in simulated time, or “virtual time,” by maintaining a time ordered event list holding time-stamped events scheduled to occur in the future, a clock indicating the current time and state variables defining the current state of the system.
Since current special- or multi-purpose parallel computers can have 104–105 PEs, it would be desirable to design a parallel computer providing for scalability of these algorithms, in both the computation phase and measurement phase of PDES. In this regard, the PDES algorithm is considered scalable if the physical time required to execute the algorithm does not change as the system to be simulated and the number of PEs available both become N times larger. Additionally, as computers become more complex and the PEs become numerous, it would be desirable to design a system that is not only fully scalable with respect to PDES, but is also scalable with respect to the number of connections between PEs while requiring as few connections between PEs as possible.